COMMENT ⊗   VALID 00006 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input acphdr % Section 3.1
C00003 00003	%folio 1 galley 1 (C) Addison-Wesley 1978	*
C00015 00004	%folio 3 galley 2 (C) Addison-Wesley 1978	*
C00025 00005	%folio 6 galley 3 (C) Addison-Wesley 1978	*
C00042 00006	\vfill\eject
C00043 ENDMK
C⊗;
\input acphdr % Section 3.1
\runninglefthead{RANDOM NUMBERS} % chapter title
\titlepage\setcount00
\null
\vfill
\tenpoint
\ctrline{SECTION 3.1 of THE ART OF COMPUTER PROGRAMMING}
\ctrline{$\copyright$ 1978 Addison--Wesley Publishing Company, Inc.}
\vfill
\runningrighthead{INTRODUCTION}
\section{3.1}
\eject
\setcount0 1
%folio 1 galley 1 (C) Addison-Wesley 1978	*
\titlepage\corners
\hjust{\def\\{\hskip 1pt}\:=C\\H\\A\\P\\T\\E\\R\hskip 10pt T\\H\\R\\E\\E}
\vskip 1 cm plus 30 pt minus 10 pt
\rjustline{\:; RANDOM NUMBERS}
\vskip .5 cm plus 1 pc minus 5 pt
\quoteformat{Anyone who considers arithmetical\cr
methods of producing random digits\cr
is, of course, in a state of sin.\cr}
\author{JOHN VON NEUMANN (1951)}
\quoteformat{Lest men suspect your tale untrue,\cr
Keep probability in view.\cr}
\author{JOHN GAY (1727)}
\quoteformat{There wanted not some beams of light\cr
to guide men in the exercise of their Stocastick faculty.\cr}
\author{JOHN OWEN (1662)}
\vskip 1 cm plus 1 pc minus 5 pt
\sectionbegin{3.1. INTRODUCTION}
N{\:cUMBERS} that are ``chosen at random'' are useful
in many different kinds of applications. For example:

\yskip\textindent{a)}{\sl Simulation.}\xskip When a computer is being used to
simulate natural phenomena, random numbers are required to make
things realistic. Simulation covers many fields, from the study
of nuclear physics (where particles are subject to random collisions)
to system engineering (where people come into, say, a bank at
random intervals).

\yskip\textindent{b)}{\sl Sampling.}\xskip It is often impractical
to examine all possible cases, but a random sample will provide
insight into what constitutes ``typical'' behavior.

\yskip\textindent{c)}{\sl Numerical analysis.}\xskip Ingenious
techniques for solving complicated numerical problems have been
devised using random numbers. Several books have been written
on this subject.

\yskip\textindent{d)}{\sl Computer programming.}\xskip Random values
make a good source of data for testing the effectiveness of
computer algorithms. This is the primary application of interest
to us in this series of books; it accounts for the fact that
random numbers are already being considered here in Chapter
3, before most of the other computer algorithms have appeared.

\yskip\textindent{e)}{\sl Decision making.}\xskip There
are reports that many executives make their decisions by flipping
a coin or by throwing darts, etc. It is also rumored that some
college professors prepare their grades on such a basis. Sometimes
it is important to make a completely ``unbiased'' decision;
this ability is occasionally useful in computer algorithms,
for example in situations where a fixed decision made each time
would cause the algorithm to run more slowly. Randomness is
also an essential part of optimal strategies in the theory of
games.

\yskip\textindent{f)}{\sl Recreation.}\xskip Rolling dice,
shuffling decks of cards, spinning roulette wheels, etc., are
fascinating pastimes for just about everybody. These traditional
uses of random numbers have suggested the name ``Monte Carlo method,''
a general term used to describe any algorithm that
employs random numbers.

\yskip People who think about this topic almost
invariably get into philosophical discussions about what the word ``random''
means. In a sense, there is no such thing as a random number;
for example, is 2 a random number? Rather, we speak of a {\sl
sequence of independent random numbers} with a specified
{\sl distribution}, and this means loosely that each number
was obtained merely by chance, having nothing to do with other
numbers of the sequence, and that each number has a specified
probability of falling in any given range of values.

A {\sl uniform} distribution on a finite set of numbers is one in which
each possible number is equally probable. A distribution is
generally understood to be uniform unless some other distribution
is specifically mentioned.

Each of the ten digits 0 through 9 will occur about $1\over10$
of the time in a (uniform) sequence of random digits. Each pair
of two successive digits should occur about $1\over100$
of the time, etc. Yet if we take a truly random sequence of
a million digits, it will not always have exactly 100,000 zeros,
100,000 ones, etc. In fact, chances of this are quite slim;
a {\sl sequence} of such sequences will have this character
on the average.

Any specified sequence of a million digits is equally as probable
as the sequence consisting of a million {\sl zeros.} Thus, if
we are choosing a million digits at random and if the first
999,999 of them happen to come out to be zero, the chance that
the final digit is zero is still exactly $1\over10$, in
a truly random situation. These statements seem paradoxical
to many people, but there is really no contradiction here.

There are several ways to formulate decent abstract definitions
of randomness, and we will return to this interesting subject
in Section 3.5; but for the moment, let us content ourselves
with an intuitive understanding of the concept.

\yskip At first, people who needed random numbers in their scientific
work would draw balls out of a ``well-stirred urn'' or would
roll dice or deal out cards. A table of over 40,000
random digits, ``taken at random from census reports,'' was
published in 1927 by L. H. C. Tippett. Since then, a number of
devices have been built to generate random numbers mechanically;
the first such machine was used in 1939 by M. G. Kendall and B.
Babington-Smith to produce a table of 100,000 random digits,
and in 1955 the RAND Corporation published a well-known
table of a million random digits obtained with the help of another
special device. A famous random-number machine called ERNIE
has been used to pick the winning numbers in the British Premium
Savings Bonds lottery.\xskip [See the articles by Kendall and Babington-Smith
in {\sl J. Royal Stat.\ Soc.}, Series A, {\bf 101} (1938), 147--166,
and Series B, {\bf 6} (1939), 51--61; see also the review of
the RAND table in {\sl Math.\ Comp.\ \bf 10} (1956), 39--43,
and the discussion of ERNIE by W. E. Thomson et al., {\sl J.
Royal Stat.\ Soc.}, Series A, {\bf 122} (1959), 301--333.]

Shortly after computers were introduced, people began to search
for efficient ways to obtain random numbers within computer programs.
A table can be used, but this method is of limited utility because
of the memory space and input time requirement, because the
table may be too short, and because it is a bit of a nuisance
to prepare and maintain the table. Machines such as ERNIE might
be attached to the computer, but this would be unsatisfactory
since it would be impractical to reproduce calculations exactly
a second time when checking out a program; and such machines
have tended to suffer from malfunctions that are difficult to
detect.

The inadequacy of these methods led to an interest in the production
of random numbers using the arithmetic operations of a computer.
John von Neumann first suggested this approach in about 1946,
using the ``middle-square'' method. His idea was to take the
square of the previous random number and to extract the middle
digits; for example, if we are generating 10-digit numbers and
the previous value was 5772156649, we square it to get
$$33317792380594909201,$$ and the next number is therefore
7923805949.

There is a fairly obvious objection to this technique: how can
a sequence generated in such a way be random, since each number
is completely determined by its predecessor? The answer is that
this sequence {\sl isn't} random, but it {\sl appears} to be. In
typical applications the actual relationship between one number
and its successor has no physical significance; hence the nonrandom
character is not really undesirable. Intuitively, the middle
square seems to be a fairly good scrambling of the previous
number.
%folio 3 galley 2 (C) Addison-Wesley 1978	*
Sequences generated in a deterministic way
such as this are usually called {\sl pseudo-random} or {\sl
quasi-random} sequences in the highbrow technical literature,
but in this book we shall simply call them random sequences,
with the understanding that they only {\sl appear} to be random.
Being ``apparently random'' is perhaps all that can be said
about any random sequence anyway. Random numbers generated deterministically
on computers have worked quite well in nearly every application,
provided that a suitable method has been carefully selected. Of course,
deterministic sequences aren't always the answer; they certainly
shouldn't replace ERNIE for the lotteries.

Von Neumann's original ``middle-square method'' has actually
proved to be a comparatively poor source of random numbers.
The danger is that the sequence tends to get into a rut, a short
cycle of repeating elements. For example, if zero ever appears
as a number of the sequence, it will continually perpetuate
itself.

Several people experimented with the middle-square method in
the early 1950s. Working with four-digit numbers instead of
10-digit ones, G. E. Forsythe tried 16 different starting values
and found that 12 of them led to sequences ending with the cycle
6100, 2100, 4100, 8100, 6100, $\ldotss$, while two of them degenerated
to zero. N. Metropolis also conducted extensive tests on the
middle-square method, mostly in the binary number system. He
showed that when 20-bit numbers are being used, there are 13
different cycles into which the sequence might degenerate, the
longest of which has a period of length 142.

It is fairly easy to restart the middle-square method on a new
value when zero has been detected, but long cycles are somewhat harder
to avoid. Exer\-cise\penalty999\ 7 discusses some interesting ways to
determine the cycles of periodic sequences,
using very little memory space.

A theoretical disadvantage of the middle-square method is given
in exercises 9 and 10. On the other hand, working with 38-bit
numbers, Metropolis obtained a sequence of about 750,000
numbers before degeneracy occurred, and the resulting $750,\!000
\times 38$ bits satisfactorily passed statistical tests for randomness.
This shows that the middle-square method {\sl can} give usable
results, but it is rather dangerous to put much faith in it
until after elaborate computationp↓xave been performed.

\yskip Many random-number generators in use today are not very good.
There is a tendency for people to avoid learning anything about
such subroutines; quite often we find that some old
method that is comparatively unsatisfactory has blindly been
passed down from one programmer to another, and today's users
have no understanding of its limitations. We shall see in this
chapter that it is not difficult to learn the most important
facts about random-number generators and their proper use.

It is not easy to invent a foolproof random-number generator.
This fact was convincingly impressed upon the author several
years ago, when he attempted to create a fantastically good
one using the following peculiar approach:

\algbegin Algorithm K (``Super-random'' number generator).
Given a 10-digit decimal number $X$, this algorithm may be used
to change $X$ to the number that should come next in a supposedly
random sequence. Although the algorithm might be expected to
yield quite a random sequence, reasons given below show that
it is, in fact, not very good at all.\xskip (The reader need not study
this algorithm in great detail except to observe its complexity;
note, in particular, steps K1 and K2.)

\algstep K1. [Choose number of iterations.]
Set $Y ← \lfloor X/10↑9\rfloor$ , the most significant digit
of $X$.\xskip (We will execute steps K2 through K13 exactly $Y + 1$
times; that is, we will apply randomizing transformations a
{\sl random} number of times.)

\algstep K2. [Choose random step.] Set $Z ← \lfloor X/10↑8\rfloor 
\mod 10$, the second most significant digit of $X$. Go to step
K$(3 + Z)$.\xskip (That is, we now jump to a {\sl random} step in the
program.)

\algstep K3. [Ensure $≥ 5 \times 10↑9$.] If $X < 5000000000$, set $X
← X + 5000000000.$

\penalty -400 % helps to balance this page with the next one
\algstep K4. [Middle square.] Replace $X$ by $\lfloor X↑2/10↑5\rfloor
\mod 10↑{10}$, i.e., by the middle of the square of $X.$

\algstep K5. [Multiply.] Replace $X$ by $(1001001001\,X)\mod
10↑{10}.$

\algstep K6. [Pseudo-complement.] If $X < 100000000$, then set
$X ← X + 9814055677;$ otherwise set $X ← 10↑{10} - X.$

\algstep K7. [Interchange halves.] Interchange the low-order
five digits of $X$ with the high-order five digits, i.e., $X
← 10↑5(X \mod 10↑5) + \lfloor X/10↑5\rfloor$, the middle
10 digits of $(10↑{10} + 1)X.$

\algstep K8. [Multiply.] Same as step K5.

\algstep K9. [Decrease digits.] Decrease each nonzero digit
of the decimal representation of $X$ by one.

\algstep K10. [99999 modify.] If $X <10↑5$, set $X ← X↑2 + 99999$;
otherwise set $X ← X - 99999.$

\algstep K11. [Normalize.] (At this point $X$ cannot be zero.)\xskip
If $X < 10↑9$, set $X ← 10X$ and repeat this step.

\algstep K12. [Modified middle square.] Replace $X$ by $\lfloor
X(X - 1)/10↑5\rfloor \mod 10↑{10}$, i.e., by the middle 10 digits
of $X(X - 1).$

\algstep K13. [Repeat?] If $Y > 0$, decrease $Y$ by 1 and return
to step K2. If $Y = 0$, the algorithm terminates with $X$ as
the desired ``random'' value.\xskip\blackslug


\yyskip (The machine-language program
corresponding to the above algorithm was intended to be so complicated
that a person reading a listing of it without explanatory comments
wouldn't know what the program was doing.)

Considering all the contortions of Algorithm K\null, doesn't it seem
plausible that it should produce almost an infinite supply of
unbelievably random numbers? No! In fact, when this algorithm
was first put onto a computer, it almost immediately converged
to the 10-digit value 6065038420, which---by extraordinary coincidence---is
transformed into itself by the algorithm (see Table 1). With another
starting number, the sequence began to repeat after 7401 values, in
a cyclic period of length 3178.
%folio 6 galley 3 (C) Addison-Wesley 1978	*
\topinsert{\tablehead{Table 1}
\ctrline{A COLOSSAL COINCIDENCE: THE NUMBER 6065038420}
\ctrline{IS TRANSFORMED INTO ITSELF BY ALGORITHM K.}
\vskip 4 pt
\hrule
\ctrline{\valign{\vskip 6pt#\vfill\vskip 6pt\cr
\halign{\lft{#}\qquad⊗\ctr{#}⊗\qquad\lft{$#$}\cr
Step⊗$X$ (after)\cr
\noalign{\vskip 3 pt\vfill}
K1⊗6065038420\cr
K3⊗6065038420\cr
K4⊗6910360760\cr
K5⊗8031120760\cr
K6⊗1968879240\cr
K7⊗7924019688\cr
K8⊗9631707688\cr
K9⊗8520606577\cr
K10⊗8520506578\cr
K11⊗8520506578\cr
K12⊗0323372207⊗Y=6\cr
K6⊗9676627793\cr
K7⊗2779396766\cr
K8⊗4942162766\cr
K9⊗3831051655\cr
K10⊗3830951656\cr
K11⊗3830951656\cr
K12⊗1905867781⊗Y=5\cr
K12⊗3319967479⊗Y=4\cr
K6⊗6680032521\cr
K7⊗3252166800\cr
K8⊗2218966800\cr}			%end of \halign
\cr					%end of first column to be \valigned
\noalign{\qquad\vrule\qquad}		%vertical rule between columns
\halign{\lft{#}\qquad⊗\ctr{#}⊗\qquad\lft{$#$}\cr
Step⊗$X$ (after)\cr
\noalign{\vskip 3 pt \vfill}
K9⊗1107855700\cr
K10⊗1107755701\cr
K11⊗1107755701\cr
K12⊗1226919902⊗Y=3\cr
K5⊗0048821902\cr
K6⊗9862877579\cr
K7⊗7757998628\cr
K8⊗2384626628\cr
K9⊗1273515517\cr
K10⊗1273415518\cr
K11⊗1273415518\cr
K12⊗5870802097⊗Y=2\cr
K11⊗5870802097\cr
K12⊗3172562687⊗Y=1\cr
K4⊗1540029446\cr
K5⊗7015475446\cr
K6⊗2984524554\cr
K7⊗2455429845\cr
K8⊗2730274845\cr
K9⊗1620163734\cr
K10⊗1620063735\cr
K11⊗1620063735\cr
K12⊗6065038420⊗Y=0\cr}			%end of \halign
\cr}}					%end of 2nd \valigned column,\ctrline
\hrule}					%end of the \topinsert 

The moral of this story is that {\sl random numbers should not
be generated with a method chosen at random.} Some theory should
be used.

\yskip In this chapter, we shall consider random-number generators
that are superior to the middle-square method and to Algorithm
K\null; the corresponding sequences are guaranteed
to have certain desirable random properties, and
no degeneracy will occur. We shall explore the reasons
for this random behavior in some detail, and we shall also consider
techniques for manipulating random numbers. For example, one
of our investigations will be the shuffling of a simulated deck
of cards within a computer program.

Section 3.6 summarizes this chapter and lists important bibliographic
sources.

\exbegin{EXERCISES}
\trexno 1. [20] Suppose
that you wish to obtain a decimal digit at random, not using
a computer. Which of the following methods would be suitable?

\penalty1000\vskip 3pt plus 3pt minus 2pt
\hang\textindent{a)}Open a telephone directory to a random
place (i.e., stick your finger in it somewhere) and use the
units digit of the first number found on the selected page.

\hang\textindent{b)}Same as (a), but use the units digit of the
{\sl page} number.

\hang\textindent{c)}Roll a die that is in the shape of a regular
icosahedron, whose twenty faces have been labeled with the digits
$0, 0, 1, 1, \ldotss, 9, 9$. Use the digit that appears on top,
when the die comes to rest.\xskip (A felt table with a hard surface
is recommended for rolling dice.)

\hang\textindent{d)}Expose a geiger counter to a source of radioactivity
for one minute (shielding yourself) and use the units digit
of the resulting count. Assume that the geiger counter displays
the number of counts in decimal notation, and that the count
is initially zero.

\hang\textindent{e)}Glance at your wristwatch; and if the position
of the second-hand is between $6n$ and $6(n + 1)$ seconds, choose
the digit $n$.

\hang\textindent{f)}Ask a friend to think of a random digit,
and use the digit he names.

\hang\textindent{g)}Ask an enemy to think of a random digit,
and use the digit he names.

\hang\textindent{h)}Assume that 10 horses are entered in a race
and that you know nothing whatever about their qualifications.
Assign to these horses the digits 0 to 9, in arbitrary fashion,
and after the race use the winner's digit.

\exno 2. [M22] In a random sequence of a million decimal digits, what is the
probability that there are exactly 100,000 of each possible
digit?

\exno 3. [10] What number follows 1010101010 in the middle-square
method?

\exno 4. [10] Why can't the value of $X$ be zero when step K11
of Algorithm K is performed? What would be wrong with the algorithm
if $X$ could be zero?

\exno 5. [15] Explain why, in any
case, Algorithm K should not be expected to provide ``infinitely
many'' random numbers, in the sense that (even if the coincidence
given in Table 1 had not occurred) one knows in
advance that any sequence generated by Algorithm K will eventually
be periodic.

\trexno 6. [M20] Suppose that we want to generate a sequence of
integers $X↓0$, $X↓1$, $X↓2$, $\ldotss$, in the range $0 ≤ X↓n < m$.
Let $f(x)$ be any function such that $0 ≤ x < m$ implies
$0 ≤ f(x) < m$. Consider a sequence formed by the rule
$X↓{n+1} = f(X↓n)$.\xskip (Examples are the middle-square method and
Algorithm K.)

\yskip\hang\textindent{a)}Show that the sequence is ultimately
periodic, in the sense that there exist numbers $λ$ and $\mu$
for which the values $X↓0$, $X↓1$, $\ldotss$, $X↓\mu$, $\ldotss$, $X↓{\mu+λ-1}$
are distinct, but $X↓{n+λ} = X↓n$ when $n ≥ \mu $.
Find the maximum and minimum possible values of $\mu$ and $λ$.

\hang\textindent{b)}(R. W. Floyd.)\xskip
Show that there exists an $n > 0$ such that
$X↓n = X↓{2n}$; and the smallest such value of $n$ lies in the range
$\mu ≤ n ≤ \mu + λ$. Furthermore the value of $X↓n$ is unique in the
sense that if $X↓n = X↓{2n}$ and $X↓r = X↓{2r}$, then $X↓r = X↓n$.

\trexno 7. [M21] (R. P. Brent, 1977.)\xskip Let $\lscr(n)$ be the least
power of 2 that is less than or equal to $n$; thus, for example, $\lscr(15)=8$
and $\lscr(\lscr(n))=\lscr(n)$.

\yskip\hang\textindent{a)}Show that, in terms of the notation in exercise 6, there
exists an $n>0$ such that $X↓n=X↓{\lscr(n)-1}$. Find a formula that expresses the
least such $n$ in terms of $\mu$ and $λ$.

\hang\textindent{b)}Apply this result to design an algorithm that can be
used in conjunction with any random-number generator of the type $X↓{n+1}=f(X↓n)$,
to prevent it from cycling indefinitely. Your algorithm should calculate the period
length $λ$, and it
should use only a small amount of memory space---you
must not simply store all of the computed sequence values!

\exno 8. [28] Make a complete examination of the middle-square
method in the case of two-digit decimal numbers.\xskip (a) We might
start the process out with any of the 100 possible values 00,
01, $\ldotss$, 99. How many of these values lead ultimately to
the repeating cycle 00, 00, $\ldotss$? [{\sl Example:} Starting
with 43, we obtain the sequence 43, 84, 05, 02, 00, 00, 00,
$\ldotss$.]\xskip (b) How many possible final cycles are there? How long
is the longest cycle?\xskip (c) What starting value or values will
give the largest number of distinct elements before the sequence
repeats?

\exno 9. [M14] Prove that the middle-square method using $2n$-digit
numbers to the base $b$ has the following disadvantage: If the
sequence includes any
number whose most significant $n$ digits are zero,
the succeeding numbers will get smaller and smaller until
zero occurs repeatedly.

\exno 10. [M16] Under the assumptions of the preceding exercise,
what can you say about the sequence of numbers following $X$
if the {\sl least} significant $n$ digits of $X$ are zero? What if
the least significant $n + 1$ digits are zero?

\trexno 11. [M26] Consider sequences of random-number generators
having the form described in exercise 6. If we choose $f(x)$
and $X↓0$ at random, i.e., if we assume that each of the $m↑m$
possible functions $f(x)$ is equally probable and
that each of the $m$ possible values of $X↓0$ is equally probable,
what is the probability that the sequence will eventually degenerate
into a cycle of length $λ = 1$?\xskip ({\sl Note:} The assumptions
of this problem give a natural way to think of a ``random''
random-number generator of this type. A method such as Algorithm
K may be expected to behave somewhat like the generator
considered here; the answer to this problem gives a measure
of how ``colossal'' the coincidence of Table 1 really is.)

\trexno 12. [M31] Under the assumptions of the preceding exercise,
what is the average length of the final cycle? What is the average
length of the sequence before it begins to cycle?\xskip (In the notation
of exercise 6, we wish to examine the average values of $λ$
and of $\mu + λ$.)

\exno 13. [M42] If $f(x)$ is chosen at random in the sense of
exercise 11, what is the average length of the {\sl longest}
cycle obtainable by varying the starting value $X↓0$?\xskip ({\sl Note:}
We have already considered the analogous problem in the case that $f(x)$ is
a random permutation; see exercise 1.3.3--23.)

\exno 14. [M38] If $f(x)$ is chosen at random in the sense of
exercise 11, what is the average number of distinct final cycles
obtainable by varying the starting value?\xskip [Cf.\ exercise 8(b).]

\exno 15. [M15] If $f(x)$ is chosen at random in the sense of
exercise 11, what is the probability that none of the final
cycles has length 1, regardless of the choice of $X↓0$?

\exno 16. [15] A sequence generated as in exercise 6 must begin
to repeat after at most $m$ values have been generated. Suppose
we generalize the method so that $X↓{n+1}$ depends on $X↓{n-1}$
as well as on $X↓n$; formally, let $f(x, y)$ be a function such
that $0 ≤ x,y < m$ implies $0 ≤ f(x, y) < m$. The sequence
is constructed by selecting $X↓0$ and $X↓1$ arbitrarily, and
then letting
$$X↓{n+1} = f(X↓n, X↓{n-1})\qquad \hjust{for } n > 0.$$
What is the maximum period conceivably attainable
in this case?

\exno 17. [10] Generalize the situation in the previous exercise
so that $X↓{n+1}$ depends on the preceding $k$ values of the
sequence.

\exno 18. [M20] Invent a method analogous to that of exercise
7 for finding cycles in the general form of random-number generator
discussed in exercise 17.

\exno 19. [M48] Solve the problems of exercises 11 through 15
for the more general case that $X↓{n+1}$ depends on the preceding
$k$ values of the sequence; each of the $m↑{m↑k}$ functions
$f(x↓1, \ldotss, x↓k)$ is to be considered equally probable.\xskip
({\sl Note:} The number of functions that yield the {\sl
maximum} period is analyzed in exercise 2.3.4.2--23.)

\vfill\eject